// 同用组件的.h函数
#pragma once
#include <iostream>
#include <assert.h>
#include <thread>
#include <mutex>
#include <algorithm>
#include <sys/mman.h>
#include <unordered_map>
using std::bad_alloc;
using std::cout;
using std::endl;
using std::min;
using std::unordered_map;

//ThreadCache的小内存块小小于256KB
static const size_t MAX_BYTES = 256; // 允许每块小内存获取的最大内存数量
//ThreadCache的freeLists的数量，一共是208
static const size_t NFREELIST = 208; // 线程自由链表的数量
static const size_t NPAGES = 129;    // 单次申请的最大连续页数
                                     // 作用：限制内存池单词向系统申请的“连续页数”上限
static const size_t PAGE_SHIFT = 13; // 当前内存池的PageCache的每个页的最大大小是8K

#ifdef _WIN64
typedef unsigned long long PAGE_ID;
#elif _WIN32
typedef size_t PAGE_ID;
#elif __linux__
typedef size_t PAGE_ID;
#endif

// 直接在堆上按页申请空间的函数
inline static void *SystemAlloc(size_t kpage)
{
#ifdef _WIN32
    void *ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#elif __linux__
    void *ptr = mmap(nullptr, kpage << 13, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
#endif
    if (ptr == nullptr || ptr == MAP_FAILED)
    {
        throw std::bad_alloc();
    }
    return ptr;
}

// 获得获得切分好小对象的头指针（void*）
static void *&NextObj(void *obj)
{
    // void*指针变量可以根据不同的操作系统位数来变成不同的大小
    // 64位是8字节，32位是4字节
    return *(void **)obj;
}
// 管理切分好的小对象的自由链表
class FreeList
{
public:
    // 头插的函数（头插相当于把内存回收到自由链表中）
    void Push(void *obj)
    {
        //_freeList是当前小内存的头指针，让obj的头几个字节（void*的大小）来指向_freeList
        // obj的头几个字节相当于链表中的next指针的作用
        // 此时obj变成了新的头节点
        NextObj(obj) = _freeList;
        // 让头指针指向obj
        _freeList = obj;
        ++_size;
    }
    // 头删的函数（头删相当于从自由链表中申请内存）
    void *Pop()
    {
        // 断言_freeList是否为空
        assert(_freeList);
        // 让obj指向_freeList，作为最后的返回值
        void *obj = _freeList;
        // 让头指针_freeList指向下一个小内存
        _freeList = NextObj(obj);
        // 返回obj
        --_size;
        return obj;
    }

    void PushRange(void *start, void *end, size_t n)
    {
        NextObj(end) = _freeList;
        _freeList = start;
        _size += n;
    }

    void PopRange(void *&start, void *&end, size_t n)
    {
        assert(n >= _size);
        start = _freeList;
        end = start;
        for (size_t i = 0; i < n - 1; ++i)
        {
            end = NextObj(end);
        }
        _freeList = NextObj(end);
        NextObj(end) = nullptr;
        _size -= n;
    }

    size_t Size()
    {
        return _size;
    }

    bool Empty()
    {
        // 如果_freeList为nullptr，说明自由链表为空
        return _freeList == nullptr;
    }

    size_t &MaxSize() // 允许外部能修改_maxSize(慢开始启动器)的函数
    {
        return _maxSize; // 返回_maxSize的引用，发女改变修改
    }

private:
    // void*类型的头指针，可以指向任意类型的地址
    void *_freeList = nullptr;
    size_t _maxSize = 1; // 用来限制当前FreeList一次能从CentralCache最多拿多少个小对象
                         // 作用：配合慢开始调节算法动态控制数量
    size_t _size = 0;
};

class SizeClass // 大小管理类
{
public:
    static size_t RoundUp(size_t size) // 根据不同的内存大小范围，按照不同的对齐模数进行向上对齐
                                       // 参数：size-原始内存大小
                                       // 返回值：对齐后的内存大小
    {
        if (size <= 128) // 如果申请的内存大小小于等于128字节
        {
            return _RoundUp(size, 8); // 返回8字节对齐后的内存大小
        }
        else if (size <= 1024) // 如果申请的内存大小小于等于1024字节
        {
            return _RoundUp(size, 16); // 返回16字节对齐后的内存大小
        }
        else if (size <= 8 * 1024) // 如果申请的内存大小小于等于8192字节
        {
            return _RoundUp(size, 128); // 返回128字节对齐后的内存大小
        }
        else if (size <= 64 * 1024) // 如果申请的内存大小小于等于65536字节
        {
            return _RoundUp(size, 1024); // 返回1024字节对齐后的内存大小
        }
        else if (size <= 256 * 1024) // 如果申请的内存大小小于等于262144字节
        {
            return _RoundUp(size, 8 * 1024); // 返回8192字节对齐后的内存大小
        }
        else // 如果申请的内存大小大于262144字节
             // 申请的内存太大了，不能申请这么多内存
        {
            assert(false); // 断言为false
            return -1;     // 返回值-1
        }
    }

    // 计算一次向系统获取几个页的函数
    //
    static size_t NumMovePage(size_t size)
    {
        assert(size > 0);
        size_t num = NumMoveSize(size); // 首先拿到ThreadCache需要的小对象数量
        size_t npage = num * size;      // 把小对象需求转换成总内存容量需求

        npage >>= PAGE_SHIFT; // PAGE_SHIFT是一个页，计算总字节数需要多少个8KB PAGE才能装下
        if (npage == 0)       // npage不能为0.最少为1
        {
            npage = 1; // 最少为1
        }
        return npage; // 返回需要申请的PAGE的数量
    }

    static inline size_t Index(size_t bytes) // 根据内存大小计算自由链表的索引
                                             // 参数：bytes-内存大小
                                             // 返回值：自由链表的索引
    {
        assert(bytes <= MAX_BYTES);                   // 断言内存大小不能大于最大内存数量
                                                      // 如果大于最大内存数量，断言为false
        static int group_array[4] = {16, 56, 56, 56}; // 数组用来存储每一段自由链表的数量
        if (bytes <= 128)                             // 如果要申请的内存小于128字节
        {
            return _Index(bytes, 3); // 返回自由链表的索引
        }
        else if (bytes <= 1024) // 如果要申请的内存大于8字节小于等于1024字节
        {
            return _Index(bytes - 128, 4) + group_array[0]; // 返回自由链表的索引
        }
        else if (bytes <= 8 * 1024) // 如果申请的内存大小大于1024小于8*1024
        {
            return _Index(bytes - 1024, 7) + group_array[1] + group_array[0]; // 返回自由链表的索引
        }
        else if (bytes <= 64 * 1024) // 如果申请的内存大小大于8*1024小于64*1024
        {
            return _Index(bytes - 8 * 1024, 10) + group_array[2] + group_array[1] + group_array[0]; // 返回自由链表的索引
        }
        else if (bytes <= 256 * 1024) // 如果申请的内存大小大于64*1024小于256*1024
        {
            return _Index(bytes - 64 * 1024, 13) + group_array[3] + group_array[2] + group_array[1] + group_array[0];
        }
        else // 申请的字节太大了
        {
            assert(false); // 断言为false
            return -1;     // 返回值-1
        }
    }

    // 慢开始的调节算法
    // 一次thread cache从中心缓存获取多少个字节对象(ThreadCache一次从CentralCache批量获取多少个小对象)
    static size_t NumMoveSize(size_t size)
    {
        assert(size > 0); // 断言size大于0
        if (size == 0)    // 判断size是否为0
        {
            return 0; // size不能为0，否则就返回0
        }
        int num = MAX_BYTES / size; // MAX_BYTES的意思是，ThreadCache单次从CentralCache获取小对象时，总字节数不能超过256字节
                                    // 本质时在总字节数不超过256的前提下，理论能拿多少个size大小的小对象
        if (num < 2)                // 下限控制，小对象最少为两个
        {
            num = 2;
        }
        if (num > 512) // 上限控制，小对象最多为512个
        {
            num = 512;
        }
        return num; // 返回ThreadCache的小对象
    }

private:
    static inline size_t _RoundUp(size_t size, size_t AlignNum) // 向上对齐函数
                                                                // 参数1：size-原始内存大小
                                                                // 参数2：AlignNum-对齐模数
                                                                // 返回值：对齐后的内存大小
    {
        return ((size + AlignNum - 1) & ~(AlignNum - 1)); // 向上对齐的公式
                                                          // 这样就能返回对应的对齐后的内存大小
    }
    static size_t _Index(size_t bytes, size_t align_shift) // 根据内存大小计算自由链表的索引
                                                           // 参数1：bytes-内存大小
                                                           // 参数2：align_shift-对齐模数的指数
                                                           // 返回值：自由链表的索引
    {
        // if (bytes % alignNum == 0)
        // {
        //     return bytes / alignNum - 1;
        // }
        // else
        // {
        //     return bytes / alignNum;
        // }
        return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1; // 根据申请的内存大小和对齐模数的指数，计算自由链表的索引
    }
};

struct Span
{
    PAGE_ID _pageID; // 大块内存起始页的页号
    size_t _n;       // 页的数量

    Span *_next; // 双向链表的结构
    Span *_prev;

    size_t _useCount; // 切好的小块内存，被分配给thread cache的计数
    void *_freeList;  // 切好的小块内存的自由链表
    size_t _objSize;  // 切好的小对象的大小
    bool _isUse = false;    //是否在被使用
};

// 带头双向循环俩表
class SpanList
{
public:
    SpanList() // SpanList的构造函数
    {
        _head = new Span;     // 创建一个哨兵节点，不存储实际的Span数据
        _head->_next = _head; // 表头的_next指向自己
        _head->_prev = _head; // 表头的_prev指向自己
    }

    void Insert(Span *pos, Span *newSpan) // 在pos前插入newSpan的函数
    {
        assert(pos);     // 断言pos不能为空
        assert(newSpan); // 断言newSpan不能为空

        Span *prev = pos->_prev; // 找到pos的前一个节点
        prev->_next = newSpan;   // 前一个节点的下一个是新节点
        newSpan->_prev = prev;   // 新节点的前一个节点是prev
        newSpan->_next = pos;    // 新节点的下一个节点是pos
        pos->_prev = newSpan;    // pos的前一个节点是newSpan
    }

    Span *PopFront()
    {
        Span *front = _head->_next;
        Erase(front);
        return front;
    }

    bool Empty()
    {
        return _head->_next == _head;
    }

    Span *Begin() //
    {
        return _head->_next;
    }

    Span *End()
    {
        return _head;
    }

    void Erase(Span *pos)
    {
        assert(pos);
        assert(pos != _head);

        Span *prev = pos->_prev;
        Span *next = pos->_next;

        prev->_next = next;
        next->_prev = prev;
    }

    void PushFront(Span *span)
    {
        Insert(Begin(), span);
    }

private:
    Span *_head;

public:
    std::mutex _mtx; // 桶锁
};